package com.algorithm.algorithm.排序算法;

import java.util.Arrays;

//以右边为轴，定义两个指针i，j，(称快慢指针)，j先走 ，遇到比轴小的时候，慢指针i向前走一步，交换位置，快指针继续前进，重复上述操作，最后将轴的位置与慢指针指的后一个位置经行交换，至此一个数的位置已经确定，
//一遍完成之后数据分为两部分接着对这两部分的数据经行相同的操作即递归，递归结束的条件即左边右边到了一个位置
public class QuickSort2 {

	public static void main(String[] args)  throws Exception{

		int a[]={8,20,18,0,3,18};

		QuickSort(a, 0,5);
		System.out.println(Arrays.toString(a));
	}

	public static void QuickSort(int[] A, int L, int R){
		if(L<R){
			boolean flag=true;
			int temp=A[R];
			int i=0;
			int j=0;
			while(j<R){
				if(A[j]<=temp){
					if(flag){
						flag=false;
					}else{
						i++;
					}
					swap(A,i,j);
					j++;
				}else{
					j++;
				}
			}
			swap(A,i+1,R);
			QuickSort(A,0,i);
			QuickSort(A,i+1,R);
		}
	}
	public static void  swap(int a[],int left,int right){
		int temp=a[right];
		a[right]=a[left];
		a[left]=temp;
	}

}
